package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 763. 划分字母区间
 * 
 * https://leetcode.cn/problems/partition-labels/
 * 
 * @author jie.deng
 *
 */
class Question0763Solution01 {
	
	public List<Integer> partitionLabels(String s) {
		List<Integer> list = new ArrayList<>();
		Map<Character, Integer> map = new HashMap<>();
		int len = s.length();
		int[] nextIdxArr = new int[len];

		for (int i = len - 1; i >= 0; i--) {
			nextIdxArr[i] = i;
			char ch = s.charAt(i);
			if (!map.containsKey(ch)) {
				map.put(ch, i);
			} else {
				nextIdxArr[i] = map.get(ch).intValue();
			}
		}

		int maxNextIdx = -1;
		int fromIdx = 0;
		for (int i = 0; i < len; i++) {
			if (nextIdxArr[i] > maxNextIdx) {
				maxNextIdx = nextIdxArr[i];
			}
			if (i == maxNextIdx) {
				list.add(i - fromIdx + 1);
				fromIdx = i + 1;
				maxNextIdx = -1;
			}
		}
		return list;
	}
    
}